package com.zj.leetcode.medium.hash;

import java.util.HashMap;

/**
 * @program: algorithm
 * @description: 连续的子数组和
 * 523 continuous-subarray-sum
 * @author: Zhang Bo
 * @create: 2022-01-14 17:05
 **/
public class ContinuousSubarraySum {
    public static void main(String[] args) {
//        int k = 6;
//        int[] nums = {23,2,4,6,7};

        int k = 6;
        int[] nums = {23,2,6,4,7};
        Solution solution = new ContinuousSubarraySum().new Solution();
        System.out.println(solution.checkSubarraySum(nums, k));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {

            HashMap<Integer, Integer> map = new HashMap<>();

            int pre = 0;
            map.put(0, 0);
            for (int i = 0; i < nums.length; i++) {
                pre = (pre + nums[i]) % k;
                if (map.containsKey(pre)) {
                    if(i + 1 - map.get(pre) >= 2){
                        return true;
                    }
                } else {
                    //使用else，保证最远的那个
                    map.put(pre, i + 1);
                }

            }

            return false;

        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
